'''
Created on Dec 26, 2012

@author: L5M
'''
import time

class PyStack():
    def __init__(self):
        self.elements = [];
        
    def push(self, element):
        self.elements.append(element);
        
    def pop(self):
        return self.elements[len(self.elements) - 1]
    
''' Bubble Sort '''
def bubbleSort(sortList):
    length = len(sortList)
    
    for i in range(0, length):
        for j in range(i + 1, length):
            if cmp(sortList[j], sortList[i]) < 0:
                sortList[i], sortList[j] = sortList[j], sortList[i]

''' Selection Sort '''
def selectSort(sortList):
    length = len(sortList)
    
    for i in range(0, length):
        m = i
        for j in range(i + 1, length):
            if cmp(sortList[j], sortList[m]) < 0:
                sortList[m], sortList[j] = sortList[j], sortList[m]

''' Insertion Sort '''
def insertSort(sortList):
    length = len(sortList)
    
    for i in range(1, length):
        j = i
        while j > 0 and cmp(sortList[j - 1], sortList[j]) > 0:
            sortList[j - 1], sortList[j] = sortList[j], sortList[j - 1]
            j -= 1
        
''' Shell Sort '''        
def shellSort(sortList):
    length = len(sortList)
    h = 1;
    while h < length / 3: h = 3 * h + 1
    
    while h >= 1:
        for i in range(h, length):
            j = i
            while j >= h and cmp(sortList[j - h], sortList[j]) > 0:
                sortList[j], sortList[j - h] = sortList[j - h], sortList[j]
                j -= h
        h = h / 3
    
''' Merge Sort '''
def mergeSort(sortList):
    sort(sortList, 0, len(sortList) - 1)
    
def sort(sortList, left, right):
    if left < right:
        center = int((left + right) / 2)
        sort(sortList, left, center)
        sort(sortList, center + 1, right)
        merge(sortList, left, right)
    
def merge(sortList, left, right):
    center = int((left + right) / 2)
    newCenter = center + 1
    temp = left
    tempList = []
    
    while left <= center and newCenter <= right:
        if sortList[left] < sortList[newCenter]:
            tempList.append(sortList[left])
            left += 1
        else:
            tempList.append(sortList[newCenter])
            newCenter += 1
            
    while left <= center:
        tempList.append(sortList[left])
        left += 1
        
    while newCenter <= right:
        tempList.append(sortList[newCenter])
        newCenter += 1
        
    newLeft = temp
    while temp <= right:
        sortList[temp] = tempList[temp - newLeft]
        temp += 1

''' Quick Sort '''
def partition(sortList, left, right):
    key = sortList[left]
    i = left + 1
    j = right
    
    while True:
        while cmp(sortList[i], key) <= 0:
            i += 1
            if i > right: break
        while cmp(sortList[j], key) > 0:
            j -= 1
            if j == left: break
            
        if i >= j: break
        
        sortList[i], sortList[j] = sortList[j], sortList[i]
    
    sortList[left], sortList[j] = sortList[j], sortList[left]
    return j
    
def quickSort(sortList):
    left = 0
    right = len(sortList) - 1
    qsort(sortList, left, right)
    
def qsort(sortList, left, right):
    if left >= right: return
    
    j = partition(sortList, left, right)
    
    qsort(sortList, left, j - 1)
    qsort(sortList, j + 1, right)

if __name__ == '__main__':
    f = file("int.txt", "r")
    sortList = []
    temp = [] 
    i = 0
    while True and i < 10000:
        line = f.readline()
        if (len(line) == 0):
            break
        sortList.append(int(line))
        temp.append(int(line))
        i += 1
    f.close()
    
    print '*' * 20 + 'Non-sort' + '*' * 20
    
    current = time.time()
    quickSort(sortList)
    print "Sort " + str(time.time() - current)
    
    current = time.time()
    
    temp.sort(lambda x,y: cmp(x, y), key=None, reverse=False)
    print "Sort " + str(time.time() - current)
    print temp
    print sortList == temp